#include <cstdlib>
#include <cstdio>
#include <iostream>
using namespace std;

struct node {
	int data;
	node *next;
};

node *head, *tail;

//=====================================sub==================================
node* preInsert(node* head, int x) {
	node *newNode = new node;
	newNode->data = x;
	newNode->next = head;
	return newNode;
}

node* preBuild(void) {
	node* newNode = NULL;
	for (int i=0; i<10; ++i)
		newNode = preInsert(newNode, i);
	return newNode;
}

node* postInsert(node* tail, int x) {
	node *newNode = new node;
	newNode->data = x;
	newNode->next = NULL;
	tail->next = newNode;
	return newNode;
}

node* postBuild(void) {
	node *newNode, *head;
	head = new node;
	head->data = 0;
	head->next = NULL;
	newNode = head;
	for (int i=1; i<10; ++i)
		newNode = postInsert(newNode, i);
	return head;
}

bool valueFind(node *head, int x) {
	node *iter = head;
	while (iter != NULL) {
		if (iter->data == x) return true;
		iter = iter->next;
	}
	return false;
}

bool posFind(node *head, int p) {
	node *iter = head;
	int cnt = 0;
	while (iter != NULL) {
		if (cnt == p) return true;
		iter = iter->next;
		++cnt;
	}
	return false;
}

bool valueInsert(node*& head, int searchValue, int insertValue) {
	node* iter = head;

	if (iter == NULL) return false;
	if (iter->data == searchValue) {
		node *newNode;
		newNode = new node;
		newNode->data = insertValue;
		newNode->next = iter->next;
		head = newNode;
		return true;
	}

	while (iter->next != NULL) {
		if (iter->next->data == searchValue) {
			node *newNode;
			newNode = new node;
			newNode->data = insertValue;
			newNode->next = iter->next;
			iter->next = newNode;
			return true;
		}
		iter = iter->next;
	}
	cout << "didn't find value " << searchValue << endl;
	return false;
}

bool posInsert(node*& head, int posValue, int insertValue) {
	node *iter = head;

	if (iter == NULL) return false;
	if (posValue == 0) {
		node *newNode;
		newNode = new node;
		newNode->data = insertValue;
		newNode->next = iter->next;
		head = newNode;
		return true;
	}

	int cnt = 1;
	while (iter->next != NULL) {
		if (cnt == posValue) {
			node *newNode;
			newNode = new node;
			newNode->data = insertValue;
			newNode->next = iter->next;
			iter->next = newNode;
			return true;
		}
		iter = iter->next;
		++cnt;
	}

	cout << "didn't find position " << posValue << endl;
	return false;
}

bool valueDelete(node*& head, int x) {
	node *iter = head;

	if (iter == NULL) return false;
	if (iter->data == x) {
		head = iter->next;
		delete iter;
		return true;
	}

	while (iter->next != NULL) {
		if (iter->next->data == x) {
			node *tmp = iter->next;
			iter->next = iter->next->next;
			delete tmp;
			return true;
		}
		iter = iter->next;
	}
	return false;
}

bool posDelete(node*& head, int x) {
	node *iter = head;

	if (iter == NULL) return false;
	if (x == 0) {
		head = iter->next;
		delete iter;
		return true;
	}

	int cnt = 1;
	while (iter->next != NULL) {
		if (cnt == x) {
			node *tmp = iter->next;
			iter->next = iter->next->next;
			delete tmp;
			return true;
		}
		iter = iter->next;
		++cnt;
	}
	return false;
}

node* getTail(node* head) {
	node* iter = head;
	if (iter == NULL) return NULL;
	while(iter->next != NULL) iter = iter->next;
	return iter;
}

void showList(node* head) {
	node* iter = head;
	while (iter != NULL) {
		cout << iter->data << " ";
		iter = iter->next;
	}
	cout << endl;
}

int getLength(node* head) {
	node* iter = head;
	int cnt = 0;
	while (iter != NULL) {
		++cnt;
		iter = iter->next;
	}
	return cnt;
}

void deleteList(node*& head) {
	while (head != NULL) posDelete(head, 0);
}
//=====================================main=================================
int main(void)
{
	head = tail = NULL;
	head = preBuild();
	cout << "front insert building finish" << endl;
	showList(head);
	deleteList(head);
	head = postBuild();
	cout << "back insert building finish" << endl;
	showList(head);
	cout << "value find result: " << valueFind(head, 5) << endl;
	cout << "position find result: " << posFind(head, 5) << endl;

	cout << "value insert result: " << valueInsert(head, 3, 100) << endl;
	cout << "position insert result: " << posInsert(head, 7, 200) << endl;
	head = preInsert(head, 300);
	cout << "front inserted" << endl;
	tail = postInsert(getTail(head), 400);
	cout << "back inserted" << endl;
	cout << "value delete result: " << valueDelete(head, 5) << endl;
	tail = getTail(head);
	cout << "position delete result: " << posDelete(head, 7) << endl;
	tail = getTail(head);
	cout << "length: " << getLength(head) << endl;
	showList(head);
	deleteList(head);
	showList(head);
	return 0;
}
